In an interactive three-dimensional graphics system, such as a system of the type disclosed in the Applicant's copending European Patent Publication No. EP-A-0531157 (not published at the first claimed priority date), data representing polygons is manipulated in three-dimensional space interactively, in response to input commands from an operator. Two-dimensional images are presented to an operator at a rate sufficient to maintain a closed feedback loop between the operator and the virtual three-dimensional environment.
A two-dimensional image is generated by rendering the three-dimensional image data onto a two-dimensional plane. For each view, "hidden surface removal" can be performed by ensuring that primitives which occlude other primitives are rendered into the two-dimensional plane either instead of the primitives which they occlude or at least after said occluded polygons. Often the occlusions are partial, therefore it is preferable to render occluded polygons prior to rendering the occluding polygons. In addition, totally invisible primitives may be culled and do not require further consideration during the rendering process. Thus, it can be appreciated that a very important aspect of the rendering process involves ensuring that the primitives are rendered in the correct order. However, determining the correct order for rendering, repeatedly for each iteration, would account for a considerable proportion of the available processing time.
A system for producing rendering order lists is disclosed in the aforesaid copending European Patent Publication, in which said lists are produced as a pre-process, using a topological sort, prior to interactive operation. If necessary, a plurality of view orientations are selected and a rendering order list is produced for each of these views. During interactive operation, one of these rendering order lists is selected by comparing the actual view orientation with the pre-processed orientations, to determine which is the closest fit. Thus, the computational overhead required during interactive operation is reduced significantly.